題目

給一個m與n，其中0 <= m <= n <= 2147483647 (2^32)，形成一個範圍[m,n]，計算m到n所有的數字做位元AND運算，並返回結果。

解法

• 使用暴力法，把所有的AND起來，當然是一個方法，但如果今天m給0，n給最大2147483647，那不知道要做多久。所以我們來觀察一下:

• 舉個例子：
  m = 11110101001 (binary)
  n = 11110101110 (binary)
  在此範圍內
  11110101001 (m)
  11110101010
  11110101011
  11110101100
  11110101101
  11110101110 (n)
  |------------|
  same part

• 能觀察到 m到n的所有數字，前面都有11110101，那這部分做AND並不會改變，但接下來後面的位元，每個位置都會出現過0，故AND完一定是0。換言之，我們要保留的是m和n，從高最位元開始，持續相同的部分，即是答案。

• 那我們能運用shift operator，只要m和n不同，就兩個數字的位元都往左移位，就如同一直把右邊砍掉，砍到剩下左邊相同的部分。最後再看shift幾次，把其中一個數字shift一樣的步數回去，就是答案了!

Code

class Solution {
public:
    int rangeBitwiseAnd(int m, int n) {
        if ((m & n) == 0) { 
            return 0; 
        }
        int shift_count = 0;
        
        while (m != n) {
            m = m >> 1;
            n = n >> 1;
            shift_count += 1;
        }
        
        return (n << shift_count);
    }
};